1 // TODO add `by` function for determining size (and children?)
  2 
  3 /**
  4  * Returns a new treemap tree layout.
  5  *
  6  * @class A tree layout in the form of an treemap. <img
  7  * src="../treemap.png" width="160" height="160" align="right"> Treemaps
  8  * are a form of space-filling layout that represents nodes as boxes, with child
  9  * nodes placed within parent boxes. The size of each box is proportional to the
 10  * size of the node in the tree.
 11  *
 12  * <p>This particular algorithm is taken from Bruls, D.M., C. Huizing, and
 13  * J.J. van Wijk, <a href="http://www.win.tue.nl/~vanwijk/stm.pdf">"Squarified
 14  * Treemaps"</a> in <i>Data Visualization 2000, Proceedings of the Joint
 15  * Eurographics and IEEE TCVG Sumposium on Visualization</i>, 2000,
 16  * pp. 33-42.
 17  *
 18  * <p>This tree layout is intended to be extended (see {@link pv.Mark#extend})
 19  * by a {@link pv.Bar}. The data property returns an array of nodes for use by
 20  * other property functions. The following node attributes are supported:
 21  *
 22  * <ul>
 23  * <li><tt>left</tt> - the cell left position.
 24  * <li><tt>top</tt> - the cell top position.
 25  * <li><tt>width</tt> - the cell width.
 26  * <li><tt>height</tt> - the cell height.
 27  * <li><tt>depth</tt> - the node depth (tier; the root is 0).
 28  * <li><tt>keys</tt> - an array of string keys for the node.
 29  * <li><tt>size</tt> - the aggregate node size.
 30  * <li><tt>children</tt> - child nodes, if any.
 31  * <li><tt>data</tt> - the associated tree element, for leaf nodes.
 32  * </ul>
 33  *
 34  * To produce a default treemap layout, say:
 35  *
 36  * <pre>.add(pv.Bar)
 37  *   .extend(pv.Layout.treemap(tree))</pre>
 38  *
 39  * To display internal nodes, and color by depth, say:
 40  *
 41  * <pre>.add(pv.Bar)
 42  *   .extend(pv.Layout.treemap(tree).inset(10))
 43  *   .fillStyle(pv.Colors.category19().by(function(n) n.depth))</pre>
 44  *
 45  * The format of the <tt>tree</tt> argument is a hierarchical object whose leaf
 46  * nodes are numbers corresponding to their size. For an example, and
 47  * information on how to convert tabular data into such a tree, see
 48  * {@link pv.Tree}. If the leaf nodes are not numbers, a {@link #size} function
 49  * can be specified to override how the tree is interpreted. This size function
 50  * can also be used to transform the data.
 51  *
 52  * <p>By default, the treemap fills the full width and height of the parent
 53  * panel, and only leaf nodes are rendered. If an {@link #inset} is specified,
 54  * internal nodes will be rendered, each inset from their parent by the
 55  * specified margins. Rounding can be enabled using {@link #round}. Finally, an
 56  * optional root key can be specified using {@link #root} for convenience.
 57  *
 58  * @param tree a tree (an object) who leaf attributes have sizes.
 59  * @returns {pv.Layout.treemap} a tree layout.
 60  */
 61 pv.Layout.treemap = function(tree) {
 62   var keys = [], round, inset, sizeof = Number;
 63 
 64   /** @private */
 65   function rnd(i) {
 66     return round ? Math.round(i) : i;
 67   }
 68 
 69   /** @private */
 70   function accumulate(map) {
 71     var node = {size: 0, children: [], keys: keys.slice()};
 72     for (var key in map) {
 73       var child = map[key], size = sizeof(child);
 74       keys.push(key);
 75       if (isNaN(size)) {
 76         child = accumulate(child);
 77       } else {
 78         child = {size: size, data: child, keys: keys.slice()};
 79       }
 80       node.children.push(child);
 81       node.size += child.size;
 82       keys.pop();
 83     }
 84     node.children.sort(function(a, b) { return a.size - b.size; });
 85     return node;
 86   }
 87 
 88   /** @private */
 89   function scale(node, k) {
 90     node.size *= k;
 91     if (node.children) {
 92       for (var i = 0; i < node.children.length; i++) {
 93         scale(node.children[i], k);
 94       }
 95     }
 96   }
 97 
 98   /** @private */
 99   function ratio(row, l) {
100     var rmax = -Infinity, rmin = Infinity, s = 0;
101     for (var i = 0; i < row.length; i++) {
102       var r = row[i].size;
103       if (r < rmin) rmin = r;
104       if (r > rmax) rmax = r;
105       s += r;
106     }
107     s = s * s;
108     l = l * l;
109     return Math.max(l * rmax / s, s / (l * rmin));
110   }
111 
112   /** @private */
113   function squarify(node) {
114     var row = [], mink = Infinity;
115     var x = node.left + (inset ? inset.left : 0),
116         y = node.top + (inset ? inset.top : 0),
117         w = node.width - (inset ? inset.left + inset.right : 0),
118         h = node.height - (inset ? inset.top + inset.bottom : 0),
119         l = Math.min(w, h);
120 
121     scale(node, w * h / node.size);
122 
123     function position(row) {
124       var s = pv.sum(row, function(node) { return node.size; }),
125           hh = (l == 0) ? 0 : rnd(s / l);
126 
127       for (var i = 0, d = 0; i < row.length; i++) {
128         var n = row[i], nw = rnd(n.size / hh);
129         if (w == l) {
130           n.left = x + d;
131           n.top = y;
132           n.width = nw;
133           n.height = hh;
134         } else {
135           n.left = x;
136           n.top = y + d;
137           n.width = hh;
138           n.height = nw;
139         }
140         d += nw;
141       }
142 
143       if (w == l) {
144         if (n) n.width += w - d; // correct rounding error
145         y += hh;
146         h -= hh;
147       } else {
148         if (n) n.height += h - d; // correct rounding error
149         x += hh;
150         w -= hh;
151       }
152       l = Math.min(w, h);
153     }
154 
155     var children = node.children.slice(); // copy
156     while (children.length > 0) {
157       var child = children[children.length - 1];
158       if (child.size <= 0) {
159         children.pop();
160         continue;
161       }
162       row.push(child);
163 
164       var k = ratio(row, l);
165       if (k <= mink) {
166         children.pop();
167         mink = k;
168       } else {
169         row.pop();
170         position(row);
171         row.length = 0;
172         mink = Infinity;
173       }
174     }
175 
176     if (row.length > 0) {
177       position(row);
178     }
179 
180     /* correct rounding error */
181     if (w == l) {
182       for (var i = 0; i < row.length; i++) {
183         row[i].width += w;
184       }
185     } else {
186       for (var i = 0; i < row.length; i++) {
187         row[i].height += h;
188       }
189     }
190   }
191 
192   /** @private */
193   function layout(node) {
194     if (node.children) {
195       squarify(node);
196       for (var i = 0; i < node.children.length; i++) {
197         var child = node.children[i];
198         child.depth = node.depth + 1;
199         layout(child);
200       }
201     }
202   }
203 
204   /** @private */
205   function flatten(node, array) {
206     if (node.children) {
207       for (var i = 0; i < node.children.length; i++) {
208         flatten(node.children[i], array);
209       }
210     }
211     if (inset || !node.children) {
212       array.push(node)
213     }
214     return array;
215   }
216 
217   /** @private */
218   function data() {
219     var root = accumulate(tree);
220     root.left = 0;
221     root.top = 0;
222     root.width = this.parent.width();
223     root.height = this.parent.height();
224     root.depth = 0;
225     layout(root);
226     return flatten(root, []).reverse();
227   }
228 
229   /* A dummy mark, like an anchor, which the caller extends. */
230   var mark = new pv.Mark()
231       .data(data)
232       .left(function(n) { return n.left; })
233       .top(function(n) { return n.top; })
234       .width(function(n) { return n.width; })
235       .height(function(n) { return n.height; });
236 
237   /**
238    * Enables or disables rounding. When rounding is enabled, the left, top,
239    * width and height properties will be rounded to integer pixel values. The
240    * rounding algorithm uses error accumulation to ensure an exact fit.
241    *
242    * @param {boolean} v whether rounding should be enabled.
243    * @function
244    * @name pv.Layout.treemap.prototype.round
245    * @returns {pv.Layout.treemap} this.
246    */
247   mark.round = function(v) {
248     round = v;
249     return this;
250   };
251 
252   /**
253    * Specifies the margins to inset child nodes from their parents; as a side
254    * effect, this also enables the display of internal nodes, which are hidden
255    * by default. If only a single argument is specified, this value is used to
256    * inset all four sides.
257    *
258    * @param {number} top the top margin.
259    * @param {number} [right] the right margin.
260    * @param {number} [bottom] the bottom margin.
261    * @param {number} [left] the left margin.
262    * @function
263    * @name pv.Layout.treemap.prototype.inset
264    * @returns {pv.Layout.treemap} this.
265    */
266   mark.inset = function(top, right, bottom, left) {
267     if (arguments.length == 1) right = bottom = left = top;
268     inset = {top:top, right:right, bottom:bottom, left:left};
269     return this;
270   };
271 
272   /**
273    * Specifies the root key; optional. The root key is prepended to the
274    * <tt>keys</tt> attribute for all generated nodes. This method is provided
275    * for convenience and does not affect layout.
276    *
277    * @param {string} v the root key.
278    * @function
279    * @name pv.Layout.treemap.prototype.root
280    * @returns {pv.Layout.treemap} this.
281    */
282   mark.root = function(v) {
283     keys = [v];
284     return this;
285   };
286 
287   /**
288    * Specifies the sizing function. By default, the sizing function is
289    * <tt>Number</tt>. The sizing function is invoked for each node in the tree
290    * (passed to the constructor): the sizing function must return
291    * <tt>undefined</tt> or <tt>NaN</tt> for internal nodes, and a number for
292    * leaf nodes. The aggregate sizes of internal nodes will be automatically
293    * computed by the layout.
294    *
295    * <p>For example, if the tree data structure represents a file system, with
296    * files as leaf nodes, and each file has a <tt>bytes</tt> attribute, you can
297    * specify a size function as:
298    *
299    * <pre>.size(function(d) d.bytes)</pre>
300    *
301    * This function will return <tt>undefined</tt> for internal nodes (since
302    * these do not have a <tt>bytes</tt> attribute), and a number for leaf nodes.
303    *
304    * <p>Note that the built-in <tt>Math.sqrt</tt> and <tt>Math.log</tt> methods
305    * can be used as sizing functions. These function similarly to
306    * <tt>Number</tt>, except perform a root and log scale, respectively.
307    *
308    * @param {function} f the new sizing function.
309    * @function
310    * @name pv.Layout.treemap.prototype.size
311    * @returns {pv.Layout.treemap} this.
312    */
313   mark.size = function(f) {
314     sizeof = f;
315     return this;
316   };
317 
318   return mark;
319 };
320